public class Code1 {
    // 最小路径和

    public int minPathSum(int[][] grid) {
        // 1、创建 dp 表
        // 2、初始化操作
        // 3、填表
        // 4、确定返回值

        // 这里 dp 表的规模是和当前的矩阵大小是一样的，但是要保存的是最小值，我们就需要表格多出一行，多出一列
        int m = grid.length;
        int n = grid[0].length;

        int dp[][] = new int[m + 1][n + 1];

        // 初始化需要注意的是，第一个存放最小值的位置左侧和上面可以为 0 ，因为要取最小值，其余的位置就需要注意我们需要取得 正无穷大
        // 先全部设置为 无穷大，之后针对单个位置进行修改
        for(int j = 0; j <= n; j++){
            dp[0][j] = Integer.MAX_VALUE;
        }
        for(int i = 0; i <= m; i++){
            dp[i][0] = Integer.MAX_VALUE;
        }
        dp[0][1] = dp[1][0] = 0;

        //填表
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                // 这里要选择出dp表中上侧和左侧的最小值，之后加上当前位置的值即可（需要注意映射关系）
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}
